#*****************************************************************************
#       Copyright (C) 2008 Arnaud bergeron <abergeron@gmail.com>
#
#  Distributed under the terms of the GNU General Public License version 2 (GPLv2)
#
#  The full text of the GPLv2 is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from word import Words
from utils import haslen
from itertools import izip, imap

class Entry:
    def __init__(self, l, r, focc, lf, rf, le, re, la, ra):
        self.l, self.r, self.focc, self.lf, self.rf, \
            self.le, self.re, self.la, self.ra = \
            l, r, focc, lf, rf, le, re, la, ra
    
    def is_lspecial(self):
        return self.le is None or self.le.la is not None
    
    def is_rspecial(self):
        return self.re is None or self.re.ra is not None
    
    def is_special(self):
        return self.is_lspecial() or self.is_rspecial()
    
    def is_bispecial(self):
        return self.is_lspecial() and self.is_rspecial()
        
    def __iter__(self):
        e = self
        while e is not None:
            yield e.l
            e = e.rf

def len_of_entry(e):
    m = -1
    while e is not None:
        e = e.rf
        m += 1
    return m

class Dictionary:
    r"""
    Class to represent in a compact manner all the factors of a word.
    
    If the optional maxfact parameter is given, only the factors smaller
    or equal in length to maxfact will be present in the dictionary.
    
    This class is a bit obscure.  This should be fixed by having someone
    understand it and document it.  Anyway, it works, and it's fast.
    
    EXAMPLES:
        sage: list(Dictionary(Words('123')('12312')))
        [word: , word: 1, word: 2, word: 12, word: 3, word: 23, word: 123, word: 31, word: 231, word: 1231, word: 312, word: 2312, word: 12312]
    """
    def __init__(self, w, maxfact=None):
        if not haslen(w):
            raise TypeError, "cannot build the dictionary of factors of %r" % (w,)
        if maxfact is None:
            maxfact = len(w)
        if maxfact > len(w):
            raise ValueError, "maxfact must not be bigger than len(word)"
        self.__comp = [0]*(maxfact + 1)
        self.__truc = [0]*(maxfact + 1)
        self.__comp[0] = 1
        self.__thetable = []
        e = self.__empty = self.__newEntry(None, None, 0, None, None, 
                                           None, None, None, None)
        self._w = w
        for (n, s) in izip(xrange(1, len(w)+1), w):
            if n <= maxfact:
                er = e
                nr = n
            else:
                er = e.df
                nr = maxfact
            e = self.__rext(er, s, n, nr)
        self.__comp = tuple(self.__comp)
        self.__truc = tuple(self.__truc)
    
    def start(self):
        return self.__vide
    
    def complexity(self):
        return self.__comp
    
    def first_occ_table(self):
        return self.__truc
    
    def __iter__(self):
        for w in imap(lambda e: self._w.parent()(e, slice(len_of_entry(e))),
                      self.__thetable):
            yield w
    
    def __newEntry(self, l, r, focc, lf, rf, le, re, la, ra):
        e = Entry(l, r, focc, lf, rf, le, re, la, ra)
        self.__thetable.append(e)
        return e
    
    def __rext(self, e, c, n, l):
        f = e.re
        while f is not None:
            if f.r == c:
                return f
            f = f.ra
        self.__comp[l] += 1
        self.__truc[l] = n
        if e.rf is not None:
            ndf = self.__rext(e.rf, c, n, l - 1)
        else:
            ndf = self.__empty
        if e == self.__empty:
            nl = c
        else:
            nl = e.l
        ndf.le = e.re = self.__newEntry(nl, c, n, e, ndf, None, None, ndf.le, e.re)
        return e.re
    
    def __lext(self, e, c, n, l):
        f = e.le
        while f is not None:
            if f.l == c:
                return f
            f = f.la
        self.__comp[l] += 1
        self.__truc[l] = n
        if e.lf is not None:
            ngf = self.__rext(e.lf, c, n, l - 1)
        else:
            ngf = self.__empty
        if e == self.__empty:
            nr = c
        else:
            nr = e.r
        ngf.le = e.le = self.__newEntry(c, nr, n, e, ngf, None, None, e.le, ngf.re)
        return e.le
